package com.ting.test.algorithms.二叉树;

import java.util.*;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 返回a和b的最低公共祖先
 * <p>
 * 利用递归的套路解答
 */
public class 判断最低公共祖先2 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        TreeNode nodeA = new TreeNode(4);
        TreeNode nodeB = new TreeNode(4);

        Info result = process(head, nodeA, nodeB);
        System.out.println(result.node);
    }

    private static Info process(TreeNode head, TreeNode nodeA, TreeNode nodeB) {
        if (head == null) {
            return new Info(null, false, false);
        }

        Info leftInfo = process(head.left, nodeA, nodeB);
        Info rightInfo = process(head.right, nodeA, nodeB);


        // 如果当前节点正好是A 或者当前节点的左子树或右子树已经找到A 那么则找到A
        boolean findA = (head == nodeA) || leftInfo.findA || rightInfo.findA;
        // 如果当前节点正好是B 或者当前节点的左子树或右子树已经找到B 那么则找到B
        boolean findB = (head == nodeB) || leftInfo.findB || rightInfo.findB;

        TreeNode node = null;

        // 如果左子树中已经找到了 那么当前节点的node就是左子树中的答案
        if (leftInfo.node != null) {
            node = leftInfo.node;
        } else if (rightInfo.node != null) {
            node = rightInfo.node;
        } else if (findA && findB) {
            // 如果左子树和右子树中都没有找到最低公共祖先，但是findA和findB又是true
            //则表明 当前节点就是最低公共祖先
            node = head;
        }

        return new Info(node, findA, findB);
    }

    static class Info {
        private TreeNode node;//表示已经找到的最低公共祖先
        private boolean findA;//找到A了没
        private boolean findB;//找到B了没

        public Info(TreeNode node, boolean findA, boolean findB) {
            this.node = node;
            this.findA = findA;
            this.findB = findB;
        }
    }

}
